package week_four;


public class MergKSortedLists_23 {
    //自己实现小根堆
    public ListNode mergeKLists(ListNode[] lists) {
        BinaryHeap heap = new BinaryHeap(lists.length);

        for (ListNode node : lists) {
            if (node != null) heap.push(node);
        }
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            tail.next = heap.poll();
            tail = tail.next;
            if (tail.next != null)
                heap.push(tail.next);
        }
        return dummy.next;
    }

    class BinaryHeap {
        ListNode[] arr;
        private int size;

        public BinaryHeap(int length) {
            arr = new ListNode[length];
            size = 0;
        }

        public void push(ListNode node) {
            size++;
            int index = size - 1;
            arr[index] = node;
            while (index > 0) {
                int fa = (index - 1) / 2;
                if (arr[index].val < arr[fa].val) {
                    swap(index, fa);
                    index = fa;
                } else break;
            }
        }

        private void swap(int index, int fa) {
            ListNode temp = arr[index];
            arr[index] = arr[fa];
            arr[fa] = temp;
        }

        public ListNode poll() {
            ListNode min = arr[0];
            swap(0, size - 1);
            //remove last
            size--;
            //heapify down.
            int index = 0;
            int left = 2 * index + 1;
            while (left < size) {
                int minChild = ((left + 1) < size) && (arr[left + 1].val < arr[left].val) ? left + 1 : left;
                if (arr[index].val > arr[minChild].val) {
                    swap(index, minChild);
                    index = minChild;
                    left = 2 * index + 1;
                } else break;
            }

            return min;
        }

        public boolean isEmpty() {
            return size() == 0;
        }

        public int size() {
            return size;
        }
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
